//给你链表的头结点 head ，请将其按 升序 排列并返回 排序后的链表 。 
//
// 
// 
//
// 
//
// 示例 1： 
//
// 
//输入：head = [4,2,1,3]
//输出：[1,2,3,4]
// 
//
// 示例 2： 
//
// 
//输入：head = [-1,5,3,4,0]
//输出：[-1,0,3,4,5]
// 
//
// 示例 3： 
//
// 
//输入：head = []
//输出：[]
// 
//
// 
//
// 提示： 
//
// 
// 链表中节点的数目在范围 [0, 5 * 104] 内 
// -105 <= Node.val <= 105 
// 
//
// 
//
// 进阶：你可以在 O(n log n) 时间复杂度和常数级空间复杂度下，对链表进行排序吗？ 
// Related Topics 链表 双指针 分治 排序 归并排序 
// 👍 1457 👎 0


//leetcode submit region begin(Prohibit modification and deletion)


import java.util.ArrayList;
import java.util.List;

/**
 * Definition for singly-linked list.
 * public class ListNode {
 *     int val;
 *     ListNode next;
 *     ListNode() {}
 *     ListNode(int val) { this.val = val; }
 *     ListNode(int val, ListNode next) { this.val = val; this.next = next; }
 * }
 */
class Solution148 {
    /**
     * 解题思路
     * 利用数组的排序完成解题
     * 解答成功:
     * 			执行耗时:18 ms,击败了14.16% 的Java用户
     * 			内存消耗:49.2 MB,击败了7.77% 的Java用户
     * @param head
     * @return
     */
    public ListNode sortList(ListNode head) {
        if(head == null) return null;

        // 链表转换数组
        List<Integer> list = new ArrayList<>();
        list.add(head.val);

        while(head.next != null) {
            int val = head.next.val;
            head = head.next;
            list.add(val);
        }


        Integer[] arr = list.toArray(new Integer[0]);
        // 归并排序
        int[] tmp = new int[arr.length];
        mergeSort(arr, 0, arr.length-1, tmp);


        // 数据转换链表
        ListNode rootNode = new ListNode();
        ListNode node = rootNode;
        for (Integer val : arr) {
            ListNode listNode = new ListNode(val);
            node.next = listNode;
            node = listNode;
        }

        return rootNode.next;
    }

    private void mergeSort(Integer[] arr, int l, int r, int[] tmp) {
        if(l < r) {
            int mid = (l+r)/2;
            // 向左递归
            mergeSort(arr, l, mid, tmp);
            // 向右递归
            mergeSort(arr, mid+1, r, tmp);
            // 合并
            merge(arr, l, mid, r, tmp);
        }
    }

    private void merge(Integer[] arr, int l, int mid, int r, int[] tmp) {
        int i=l, j=mid+1, t=0;
        while(i<=mid && j<=r) {
            tmp[t++] = (arr[i]<=arr[j]) ? arr[i++] : arr[j++];
        }

        while(i<=mid) {
            tmp[t++] = arr[i++];
        }

        while(j<=r) {
            tmp[t++] = arr[j++];
        }

        t=0;
        int left = l;
        while(left <= r) {
            arr[left++] = tmp[t++];
        }
    }

    /**
     * 使用链表的插入排序 Time Limit Exceeded
     * @param head 初始链表
     * @return
     */
    public ListNode sortList2(ListNode head) {
        if(head == null) return null;

        ListNode root = new ListNode();

        while(head != null) {
            int val = head.val;
            ListNode temp = root;
            while(temp != null) {
                // 说明找到了链表的结尾还没有匹配到比val大的元素
                if(temp.next == null) {
                    // 直接将当前元素放入链表末尾
                    ListNode nextNode = new ListNode(val);
                    temp.next = nextNode;
                    break;
                }

                if(temp.next.val > val) {
                    // 说明匹配到了比val大的元素
                    ListNode nextNode = new ListNode(val);
                    nextNode.next = temp.next;
                    temp.next = nextNode;
                    break;
                }
                temp = temp.next;
            }
            head = head.next;
        }

        return root.next;
    }

    /**
     * 解题思路：
     * 直接对链表进行归并排序
     *
     * 解答成功:
     * 			执行耗时:8 ms,击败了41.95% 的Java用户
     * 			内存消耗:47.7 MB,击败了19.91% 的Java用户
     * @param head
     * @return
     */
    public ListNode sortListAnswer(ListNode head) {
        if (head == null) {
            return null;
        }
        ListNode mid = getMid(head);
        if (mid.next == null) {
            return mid;
        }
        ListNode headB = mid.next;
        mid.next = null;
        return mergeTwoList(sortListAnswer(head), sortListAnswer(headB));
    }
    public ListNode getMid(ListNode head) {
        head = new ListNode(0, head);
        ListNode slow = head;
        ListNode fast = head;
        while (fast != null && fast.next != null) {
            slow = slow.next;
            fast = fast.next.next;
        }
        return slow;
    }
    public ListNode mergeTwoList(ListNode l1, ListNode l2) {
        ListNode dump = new ListNode();
        ListNode last = dump;
        while (l1 != null && l2 != null) {
            if (l1.val <= l2.val) {
                last.next = l1;
                l1 = l1.next;
            } else {
                last.next = l2;
                l2 = l2.next;
            }
            last = last.next;
        }
        if (l1 != null) {
            last.next = l1;
        }
        if (l2 != null) {
            last.next = l2;
        }
        return dump.next;
    }

    public static void main(String[] args) {
        ListNode listNode11 = new ListNode(4);
        ListNode listNode12 = new ListNode(2);
        ListNode listNode13 = new ListNode(1);
        ListNode listNode14 = new ListNode(3);
        ListNode listNode15 = new ListNode(5);
        listNode14.next = listNode15;
        listNode13.next = listNode14;
        listNode12.next = listNode13;
        listNode11.next = listNode12;

        //ListNode listNode = new Solution148().sortList2(listNode11);
        //System.out.println(listNode);

    }
}
//leetcode submit region end(Prohibit modification and deletion)
